/*
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.
*/

class Solution {
public:
    bool ispair(char c1, char c2) {
        if ((c1 == '(' && c2 == ')')  ||
             (c1 == '[' && c2 == ']') ||
             (c1 == '{' && c2 == '}')) {
            return true;
        }
        return false;
    }
    bool isValid(string s) {
        stack<char> st;
        for (int i = 0; i < s.length(); i++) {
            if ((s[i] == '(') || (s[i] == '[') || (s[i] == '{')) {
                st.push(s[i]);
            } else if ((s[i] == ')') || (s[i] == ']') || (s[i] == '}')) {
                // st.empty() is needed to avoid crash
                if (!st.empty() &&
                    ispair(st.top(), s[i])) {
                    st.pop();
                } else {
                    return false;
                }
            } else {
                continue;
            }
        }
        return (st.empty())?true:false;
    }
};
